import java.util.Map;

/*
 * @lc app=leetcode.cn id=146 lang=java
 *
 * [146] LRU 缓存机制
 */

// @lc code=start
class LRUCache {
    /**
     * 双向链表，记录key-value
     * 这里需要key的原因是，如果你在双向链表中删去最少使用的节点后，还需要在map中删去对应key的节点，如果链表只记录value值，是没办法反过去寻值的。
     * 
     * map的作用是快速判断某个key是否存在，以及它的value,用于数据访问
     * linkedList的作用是排序每个节点的使用频率，用于排序
     */
    public class DLinkedNode{
        int key,value;
        DLinkedNode prev,next;//前后指针
        public DLinkedNode(){};
        public DLinkedNode(int k , int v){
            this.key=k;
            this.value=v;
        }
    }
    Map<Integer,DLinkedNode> cache = new HashMap<>();
    DLinkedNode head,tail;//空的头尾指针
    int size;
    int capability;

    public LRUCache(int capacity) {
        this.capability=capacity;
        this.size=0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev=head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if(node==null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if(node == null){//key不存在
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key, newNode);//先在map中放入这个节点
            addToHead(newNode);//然后在链表中将此节点放入头部
            size++;
            if(size>capability){//如果超过容量，需要删除尾部节点（即最近最少使用节点）
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        }else{//有该key，直接更新key，并前移
            node.value = value;
            moveToHead(node);
        }
    }

    public void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    public void removeNode(DLinkedNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    public void addToHead(DLinkedNode node){
        node.prev = head;
        node.next =head.next;
        head.next.prev=node;
        head.next=node;
    }
    public DLinkedNode removeTail(){
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
// @lc code=end

